#include <iostream>

using namespace std;

/*
Given an array, start from the first element and reach the last by jumping. 
The jump length can be at most the value at the current position in the array. 
Optimum result is when you reach the goal in minimum number of jumps. Example:
Given array A = {2,3,1,1,4}
Possible ways to reach the end (index list)
    0,2,3,4 (jump 2 to index 2, and then jump 1 to index 3 and then jump 1 to index 4)
    0,1,4 (jump 1 to index 1, and then jump 3 to index 4)
Since second solution has only 2 jumps it is the optimum result.

*/

//Define MAX 1 less so that adding 1 doesn't make it 0  
#define MAX 0xFFFFFFFE;  

/* 
The following solution time complexity is O(n^2)
*/
unsigned int MinJumpSteps(int *array, int n)  
{  
    unsigned int *result = new unsigned int[n];  
    int i, j;  
        
    //Boundry conditions. The first item cannot be 0  
    if (n==0 || array[0] == 0)  
		return MAX;  
          
    //no need to jump at first element  
	result[0] = 0;  
    for (i = 1; i < n; i++)  
    {  
		result[i] = MAX;  
		for (j = 0; j < i; j++)  
		{  
			//check possible jump is from j to i  
			if (array[j] >= (i-j))      
			{  
     			//check if better solution available  
				if ((result[j] + 1) < result[i])   
					result[i] = result[j] + 1;  
			}  
		}  
    }  
        
    //return result[n-1]  
    unsigned int answer = result[n-1];  
    delete[] result;  
  
    return answer;  
}  

unsigned int MinJumpSteps2(int *array, int n)  
{  
    unsigned int *result = new unsigned int[n];  
    int i, j;  
        
    //Boundry conditions. The first item cannot be 0  
    if (n==0 || array[0] == 0)  
		return MAX;  
          
    //no need to jump at first element  
	for (i = 1; i < n; i++)  
    {
		result[i] = MAX;  
	}

    for (i = 1; i < n; i++)  
    {  
		result[i] = MAX;  
		for (j = 0; j < i; j++)  
		{  
			//check possible jump is from j to i  
			if (array[j] >= (i-j))      
			{  
     			//check if better solution available  
				if ((result[j] + 1) < result[i])   
					result[i] = result[j] + 1;  
			}  
		}  
    }  
        
    //return result[n-1]  
    unsigned int answer = result[n-1];  
    delete[] result;  
  
    return answer;  
}  

int main()
{
	int minSteps = 0;
	int array[] = {2,3,1,1,4};
	int n = sizeof(array)/sizeof(array[0]);

	for(int i=0; i<n; i++)
		cout<<array[i]<<" ";
	cout<<endl;

	minSteps = MinJumpSteps(array, n);
	cout<<"\nThe minimum jump steps (algorithm 1) are "<<minSteps<<endl;

	minSteps = MinJumpSteps2(array, n);
	cout<<"\nThe minimum jump steps (algorithm 2) are "<<minSteps<<endl;

	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}
